/**
 * 
 */
package tree.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class PathSumII {

	/**
	Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
	For example:
	Given the below binary tree and sum = 22,

	          5
	         / \
	        4   8
	       /   / \
	      11  13  4
	     /  \    / \
	    7    2  5   1

	return

	[
	[5,4,11,2],
	[5,8,4,5]
	]
	 */
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		pathSumHelp(root, sum, new ArrayList<Integer>(), result);
		return result;

	}

	public void pathSumHelp(TreeNode root, int sum, ArrayList<Integer> buffer,
			ArrayList<ArrayList<Integer>> result) {
		if (root == null)
			return;

		buffer.add(root.val);
		if (root.val == sum && root.left == null && root.right == null) {
			result.add(new ArrayList<Integer>(buffer));
		}

		pathSumHelp(root.left, sum - root.val, buffer, result);
		pathSumHelp(root.right, sum - root.val, buffer, result);

		if (buffer.size() > 0)
			buffer.remove(buffer.size() - 1);
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public PathSumII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
